package org.itheima.hello数据结构.哈希表.哈希冲突;

public class 解析 {

    /*
    上一节提到，通常情况下哈希函数的输入空间远大于输出空间，因此理论上哈希冲突是不可避免的。
    比如，输入空间为全体整数，输出空间为数组容量大小，则必然有多个整数映射至同一桶索引。哈希冲
    突会导致查询结果错误，严重影响哈希表的可用性。为了解决该问题，每当遇到哈希冲突时，我们就进
    行哈希表扩容，直至冲突消失为止。此方法简单粗暴且有效，但效率太低，因为哈希表扩容需要进行大
    量的数据搬运与哈希值计算。为了提升效率，我们可以采用以下策略。

        改良哈希表数据结构，使得哈希表可以在出现哈希冲突时正常工作。
        仅在必要时，即当哈希冲突比较严重时，才执行扩容操作。
    哈希表的结构改良方法主要包括“链式地址”和“开放寻址”。
    */

//        改良哈希表数据结构，使得哈希表可以在出现哈希冲突时正常工作。
//        哈希表的结构改良方法主要包括“链式地址”和“开放寻址”。
//        仅在必要时，即当哈希冲突比较严重时，才执行扩容操作。

    /*
    链式地址存在以下局限性。

    占用空间增大：链表包含节点指针，它相比数组更加耗费内存空间。
    查询效率降低：因为需要线性遍历链表来查找对应元素。*/

    /*开放寻址（open addressing）不引入额外的数据结构，而是通过
    “多次探测”来处理哈希冲突，探测方式主要包括线性探测、平方探测和多次哈希等。*/
    /*1.   线性探测
    线性探测采用固定步长的线性搜索来进行探测，其操作方法与普通哈希表有所不同。
    插入元素：通过哈希函数计算桶索引，若发现桶内已有元素，则从冲突位置向后线
    性遍历（步长通常为1），直至找到空桶，将元素插入其中。查找元素：若发现哈希
    冲突，则使用相同步长向后进行线性遍历，直到找到对应元素，返回 value 即可；
    如果遇到空桶，说明目标元素不在哈希表中，返回 None 。*/

    //线性探测容易产生“聚集现象
    //值得注意的是，我们不能在开放寻址哈希表中直接删除元素。这是因为删除元素会在数组内产生一个空桶
    // None ，而当查询元素时，线性探测到该空桶就会返回，因此在该空桶之下的元素都无法再被访问到，程
    // 序可能误判这些元素不存在


    //为了解决该问题，我们可以采用懒删除（lazy deletion）机制：
    //然而，懒删除可能会加速哈希表的性能退化。


    /*
    * Python 采用开放寻址。字典 dict 使用伪随机数进行探测。
    Java 采用链式地址。自 JDK 1.8 以来，当 HashMap 内数组长度达到 64 且链表长度达到 8 时，链表会转换为红黑树以提升查找性能。
    Go 采用链式地址。Go 规定每个桶最多存储 8 个键值对，超出容量则连接一个溢出桶；当溢出桶过多时，会执行一次特殊的等量扩容操作，以确保性能。*/




















}
